package com.ainge.easystudy.binary.tree;

import java.util.Arrays;

/**
 * 简单二叉堆，最大堆
 * 堆排序的思路：
 * 升序：
 *   1、构造最大堆，可以通过循环数组，一个个元素插入的形式构造最大堆，
 *   也可以通过非叶子节点下沉构造最大堆（更优）。
 *   2、当构造最大堆完成后，依次取出最大堆到数组末尾，继续heapity。
 *
 * @author: Ainge
 * @Time: 2021/9/14 22:30
 */
public class SimpleBinaryHeap {

    public static void main(String[] args) {
        int[] arr = new int[]{7,1,3,10,5,2,8,9,6};
        // 1.1依次插入的方式构造最大堆。
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr,i);
        }
        System.out.println(Arrays.toString(arr));
        // 1.2非叶子节点，下沉的方式构造最大堆
        // 1.1跟1.2是等价的，用哪种方式都可以
        buildHeap(arr);
        System.out.println(Arrays.toString(arr));
        // 排序
        for (int i = 0; i < arr.length; i++) {
            // 把最大值放到数组最末尾
            swap(arr,0,arr.length - i -1);
            // 相当于根节点被移走了，继续heapity
            heapify(arr,0,arr.length - i -1);
        }
        System.out.println(Arrays.toString(arr));
    }


    public static void buildHeap(int[] arr){
        // 从最后一个非叶子节点，开始heapify size= 2*n +2 =2(n+1)
        for (int i = ((arr.length >>> 1) - 1); i >=0 ; i--) {
            heapify(arr,i,arr.length);
        }
    }

    /**
     * index节点上浮调整
     * @param arr 待调整的堆
     */
    public static void heapInsert(int[] arr,int index){
        int parentIndex;
        while (index > 0 && arr[index] > arr[parentIndex = (index - 1) >> 1]){
            // 交换
            swap(arr,index,parentIndex);
            index = parentIndex;
        }
    }

    public static void heapify(int[] arr,int index,int heapSize){
        // 左孩子下标
        int left = (index << 1) + 1;
        while (left < heapSize){
            // 两个孩子中，谁的值大，就把谁的下标给largest
            int largest = (left + 1 < heapSize && arr[left + 1] > arr[left])? left + 1: left;
            // 父亲与较大孩子比较，如果父亲较大，则不需要继续
            if(arr[largest] <= arr[index]){
                break;
            }
            swap(arr,largest,index);
            index = largest;
            left = (index << 1) + 1;
        }
    }


    /**
     * 交互数组下标两个元素位置
     * @param arr 数组
     * @param i  下标i
     * @param j  下标j
     */
    public static void swap(int[] arr,int i,int j){
        if(arr.length <= 0 || i == j){
            return;
        }
        if(i < 0 || i >= arr.length){
            return;
        }
        if(j < 0 || j >= arr.length){
            return;
        }
        // 利用异或的特性,0^a=a,a^a=0,a^b^c = a^c^b
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}
